import logging
logging.basicConfig(format='%(levelname)s:%(message)s', level=logging.DEBUG)

###
# start of the get largest frequent sub pattern
###
def get_common_length(s1,s2,sindex1=None,sindex2=None):
    """
    sindex1 and sindex2 is used for prevent the overlap
    the return value must be multiplier of 2
    """
    #print s1,s2
    # TODO this function need detailed debug 
    # error for (18, 21, '181920') (29, 32, '181920') 1819 4 2
    
    if sindex1 != None and sindex2 != None:
        tmplen = abs(sindex1-sindex2)
    else:
        tmplen = 10000000
    tmplen = min(len(s1),tmplen)
    tmplen = min(len(s2),tmplen)

    if s1[:tmplen] == s2[:tmplen]:
        return tmplen

    i = 0
    for i in range(tmplen):
        if s1[:i] == s2[:i]:
            #print i,s1[:i],s2[:i]
            continue
        break

    # i is the first different one, i should be the real length
    if i % 2 == 0:
        return i
    else:
        return i-1



def get_frequent_common(str_list,bitnum):
    """
    : params str_list : 
    : params bitnum : number of code to represent one sentence
    : return : 

    1 get the most frequent substring of string list str_list
    1.1 get all the repeated common string, local longest
    1.2 get the longest one from the most frequent ones
    """
    # step 1 : get all the substrings using the suffix tree method
    suffix_array = []
    for tmp_str in str_list:
        for i in range( len(tmp_str)/bitnum ):
            suffix_array.append( tmp_str[i*bitnum:] )
    suffix_array.sort()

    sub_str_list = []
    for i in range(len(suffix_array)-1):
        cl = get_common_length( suffix_array[i], suffix_array[i+1] )
        if cl == 0:
            continue
        sub_str_list.append( suffix_array[i][:cl] )
    sub_str_list = list(set(sub_str_list))

    # TODO change to logging system
    print sub_str_list

    # step 2 : get the count of each sub str
    sub_str_count_list = []
    for sub_str in sub_str_list:
        c = 0
        for tmp_str in str_list:
            c += tmp_str.count(sub_str)
        sub_str_count_list.append( ( sub_str,c) )
    
    # step 3 : sort and get the best
    sub_str_count_list.sort( lambda x,y: 10*(y[1]-x[1])+len(y[0])-len(x[0]))
    """
    for sub_str,c in sub_str_count_list:
        #print sub_str,c
        dono = 1
    """

    return sub_str_count_list[0][0]

###
# end of get largest common sub string
###

if __name__ == "__main__":
    assert get_common_length('181920','181920',18,29) == 6
    assert get_common_length('18192001','18192002',18,29) == 6
    assert get_common_length(\
            '09101112131415151715152015153815154141',\
            '09101112131415151715152021222309101112131415151715152015153815154141',\
            48,18) == 24
